Ch 9 Routing I

utg

CPE 426 Computer Networks

Chapter 9:

Text Chapter 18&27: Internet

Routing Part I:

TOPICS

„

Chapter 27: Internet Routing and Routing Protocols

„

27.1 Introduction

„

27.2 Static vs Dynamic Routing

„

Extra: Router Configuration in Network

„

27.3 Static Routing and Default Route

„

Extra: Examples of Static Routing

„

BREAK

„

27.4 Dynamic Routing and Router

„

27.5 Routing in Global Internet

„

27.6 Autonomous System Concept

„

27.7 Two Types of Routing Protocol

„

27.8 Routes and Data Traffic

„

Extra: Bellman-Ford Algorithm Review

„

Extra: Dijkstra Algorithm Review

Chapter 27:Internet Routing and

Routing Protocol

„ ล ักษณะการส่ง Packet ใน IP Network จะส่ง

ทีละ Hop จาก Network หนึ่ง ไปย ังอีก

Network หนึ่ง

„ Router จะทําหน้าที่ด ังกล่าว เนื่องจาก Router เป็นต ัวเชื่อมระหว่าง Network

„ การส่งจะดูที่ส่วน Prefix ของ IP Address

ด ังน ั้น Router จะต้อง Run IP Protocol คือ

ทํางานในระด ับ Layer 3

„ ที่ Router จะมีตารางชื่อ Routing Table ที่

กําหนด IP Address ของ Next Hop

Chapter 27: 27.2 Static vs

Dynamic Routing

„ การทํา Routing ทําได้สองแบบ

„ Static Routing: หมายถึงตาราง Routing Table ของ

Router แต่ละตัวจะไม่เปลี่ยน ปกติตารางนี้จะถูกกําหนด

จาก Network Administration

„ คือตารางนี้จะได ้จากการทํา Configuration ของ Router

„ Dynamic Routing: หมายถึงตาราง Routing Table

สามารถเปลี่ยนได ้ ตามสภาวะความคับคั่งของ Network ขณะนั้น โดยมันจะมีการ Update ตลอดเวลา

„ ตารางนี้ได ้จากการกําหนดให ้ Router ทําการ Run Routing Protocol

„ ในแต่ละ Routing Protocol ตัว Router จะทําการแลกเปลี่ยน

ข ้อมูลกันเอง โดยผู ้ดูแล Network ไม่ต ้องมาเกี่ยวข ้อง จากนั้น

Router แต่ละตัวจะสร ้างตาราง Routing Table จากข ้อมูลที่มัน

รวบรวมได ้ เมื่อข ้อมูลที่ได ้รับเปลี่ยน เนื่องจาก Network เปลี่ยน

มันจะคํานวณตารางใหม่ และปรับให ้เข ้ากับสภาพของ Network ที่

เปลี่ยนไป

Chapter 27: 27.3 Static Routing

in Host and Default Route

„

ข้อดีของ Static Routing คือง่าย และไม่ต้องใช้

Routing Software(Router จะทํางานน้อยลง)

นอกจากนี้จะไม่ใช้ Resource ของ Network เพราะ

Router ไม่ต้องแลกเปลี่ยนข้อมูลก ัน

„

แต่ข้อเสียคือ ตารางเปลี่ยนไม่ได้ ถ้ามี Link Down หรือ Router Down เส้นทางน ั้นจะใช้ไม่ได้ ทําให้การ

ส่งข้อมูลที่กําหนดเส้นทางน ั้นหยุดชะง ัก

„

นอกจากนี้แล ้ว Static Routing จะจํากัดที่ Network ขนาดเล็ก เช่น

ระหว่าง LAN ขององค์กร การเชื่อมต่อกับ Internet จะไม่ใช ้ Static Routing

„

หรือใช ้กําหนดสําหรับ Host ที่เชื่อมต่อกับ Network ที่มีทางออก

ผ่าน Router ตัวเดียว(คือค่า Gateway)

„

การใช้ Static Route ควรมีการกําหนด Default

Route เสมอ

„

การทํา Static Route ต้องตรวจสอบให้ดีว่าจะไม่มี

Route Loop

Chapter 27: 27.3 Static Routing

in Host and Default Route

การกําหนด Interface สําหร ับ

Router

„

แต่ละ Interface ของ Router จะต้องมี IP Address ที่ตรงก ับแต่ละ Network ที่ Interface เชื่อมต่อ

(Prefix เหมือนก ัน แต่ Suffix ต่างก ัน)

58.42.96.0/19

58.42.96.1

58.42.96.2

200.18.95.1

195.3.0.193

R1

R2

200.18.95.0/24

195.3.0.192/26

R3

R4

195.3.0.194

200.18.95.2

70.12.0.1

70.12.0.2

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

„

สายที่เชื่อมต่อโดยตรงระหว่าง Router จะต้องถือเป็น

หนึ่ง Network เช่นก ัน แต่ Network นี้เป็นแค่ทางผ่าน

ของข้อมูล ไม่จําเป็นต้องกําหนดใน Routing Table 58.42.96.0/19

58.42.96.1

200.18.95.1 R1

R4 195.3.0.193

R2

200.18.95.0/24

195.3.0.192/26

R3

70.12.0.1

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

„

สายระหว่าง Router สามารถ Subnet จาก Private IP ได้ และ

ต้องการเพียงสอง Host Address ซึ่งปกติจะใช้ /30 ก็พอ เช่น Sub จาก 192.168.100.0/24 จะได้ 64 Subnet

Subnet 192.168.100.4/30 : Host Range 192.168.100.5-192.168.100.6; Broadcast 192.168.100.7

192.168.100.4/30

58.42.96.0/19

192.168.100.8/30

58.42.96.1

.6

.9

R1 .5

.10 R4

200.18.95.1

195.3.0.193

R2

200.18.95.0/24

195.3.0.192/26

.18

R3

.13

.17

.14

70.12.0.1

192.168.100.12/30

192.168.100.16/30

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

„

การกําหนด Static Routing Table ให้ก ับ Router แต่ละต ัวทําได้จาก

การกําหนดเส้นทางส่งข้อมูลจาก Router ไปย ังทุกๆ Network (Network ที่เป็น Transit ไม่ต้องกําหนด เพราะไม่มี Host ปลายทาง) จากน ั้นกําหนดเส้นทางหนึ่งให้เป็น Default Route เช่น R1

58.42.96.0/19

58.42.96.1

.6

.9

192.168.100.4/30

192.168.100.8/30

.5

.10

200.18.95.1

R2

195.3.0.193

200.18.95.0/24

R1

R4

195.3.0.192/26

.18

.13

R3

192.168.100.12/30

192.168.100.16/30

.17

.14

70.12.0.1

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

NW

Mask

Next Hop

200.18.95.0

255.255.255.0

Direct

70.12.0.0

255.255.0.0

192.168.100.17

58.42.96.0

255.255.224.0

192.168.100.6

195.3.0.192

255.255.255.192 192.168.100.6

0.0.0.0

0.0.0.0

192.168.100.17

58.42.96.0/19

58.42.96.1

.6

.9

192.168.100.4/30

192.168.100.8/30

.5

.10

200.18.95.1

R2

195.3.0.193

200.18.95.0/24

R1

R4

195.3.0.192/26

.18

.13

R3

192.168.100.12/30

192.168.100.16/30

.17

.14

70.12.0.1

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

R2 Routing Table

58.42.96.0/19

58.42.96.1

.6

.9

192.168.100.4/30

192.168.100.8/30

.5

.10

200.18.95.1

R2

195.3.0.193

200.18.95.0/24

R1

R4

195.3.0.192/26

.18

.13

R3

192.168.100.12/30

192.168.100.16/30

.17

.14

70.12.0.1

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

R3 Routing Table

58.42.96.0/19

58.42.96.1

.6

.9

192.168.100.4/30

192.168.100.8/30

.5

.10

200.18.95.1

R2

195.3.0.193

200.18.95.0/24

R1

R4

195.3.0.192/26

.18

.13

R3

192.168.100.12/30

192.168.100.16/30

.17

.14

70.12.0.1

70.12.0.0/16

การกําหนด Interface สําหร ับ

Router

R4 Routing Table

58.42.96.0/19

58.42.96.1

.6

.9

192.168.100.4/30

192.168.100.8/30

.5

.10

200.18.95.1

R2

195.3.0.193

200.18.95.0/24

R1

R4

195.3.0.192/26

.18

.13

R3

192.168.100.12/30

192.168.100.16/30

.17

.14

70.12.0.1

70.12.0.0/16

Chapter 27: 27.4 Dynamic

Routing and Router

„ ปกต ิ Router ใน Internet จะใช้ Dynamic

Routing

„ เพื่อให ้มีการแลกเปลี่ยน Routing Information ระหว่าง

กัน

„ Static Routing อาจจะถูกใช้ในกรณีที่

Customer เชื่อมต่อก ับ ISP ผ่าน Router ซึ่ง

ในกรณีนี้มีทางออก Internet เพียงทางเดียว

และไม่จําเป็นต้องใช้ Dynamic Routing

„ หรือ Static Routing อาจจะใช้ภายในองค ์กร

เพื่อเชื่อมต่อ LAN หลายๆวงภายในอาคาร

Chapter 27: 27.4 Dynamic

Routing and Router

„

Router จะรู้จ ัก Network ที่เป็น Direct Connect เท่าน ั้น

„

การที่ Router จะรู้จ ัก Network อื่น ม ันจะต้องเรียนรู้

มาจาก Router ต ัวอื่นที่ต่อโดยตรงก ับ Network น ั้น

„

ใน Static Routing จะไม่มีวิธีที่ Router จะเรียนรู้ได้

„

ด ังน ั้นการเรียนรู้ต้องมีการกําหนดจาก Software ใน

Routing Protocol ใน Dynamic Routing

„

ด้วยการเรียนรู้นี้เอง ทําให้ Router สามารถปร ับตาราง

ของตนได้อย่างเหมาะสม ตามสภาพ Network เป็นผล

ให้ตาราง Routing เป็น Dynamic

Chapter 27: 27.4 Dynamic

Routing and Router

„

จากรูป R1 รู้จ ัก 200.18.95.0/24 และ

58.42.96.0/19 แต่ไม่รู้จ ัก 195.3.0.192/26

„

R2 รู้จ ัก 58.42.96.0/19 และ 195.3.0.192/26 แต่ไม่

รู้จ ัก 200.18.95.0/24

„

R1 และ R2 แลกเปลี่ยนข้อมูลก ันผ่าน 58.42.96.0/19

ทําให้ Router แต่ละต ัวรู้จ ัก Network อื่นๆ

„

ถ้า 195.3.0.192 เกิดล่ม R2 จะรู้ และสามารถบอก

ต่อไปย ัง R1 ได้ ว่า 195.3.0.192/26 Unreachable

„

ถ้า R2 ล่ม ทําให้ R1 ไม่สามารถติดต่อได้ ด ังน ั้น R1 จะ

Mark ว่า 195.3.0.192/26 เป็น Unreachable เช่นก ัน

R1

R2

200.18.95.0/24

58.42.96.0/19

195.3.0.192/26

Chapter 27: 27.5 Routing in

Global Internet

„

Internet ประกอบด้วย Router มากมาย ถ้าจะให้

Router ทุกต ัวแลกเปลี่ยนข้อมูลก ับ Router ทุกต ัว จะ

ทําให้ Routing Traffic มีมหาศาล

„

เพื่อจําก ัดจํานวน Traffic ใน Internet จะใช้การทํา

Routing แบบเป็นลําด ับช ั้น (Hierarchy) โดยมีการ

แบ่งกลุ่มของ Router และมีการแลกเปลี่ยนข้อมูล

ภายในกลุ่ม จากน ั้นจะมี Router ที่เป็นต ัวแทนของ

กลุ่มทําการแลกเปลี่ยนข้อมูลก ับภายนอก

„

Routing Protocol ภายในกลุ่ม จะแตกต่างจาก

Routing Protocol ระหว่างกลุ่ม

„

ขนาดของกลุ่มจะไม่จํากัด ขึ้นอยู่กับขนาดขององค์กร

„

แต่ละองค์กรที่เป็นเจ ้าของกลุ่ม มีสิทธิจะเลือก Routing Protocol อย่างไรก็ได ้ ที่อยู่ภายในกลุ่ม

„

แต่ Routing Protocol ที่ใช ้แลกเปลี่ยนข ้อมูลระหว่างกลุ่มจะต ้อง

เป็น Protocol เดียวกัน

Chapter 27: 27.6 Autonomous

System Concept

„ แต่ละกลุ่มของ Router ที่ดูแลจ ัดการ

โดยองค์กรเดียว เราเรียกว่า

Autonomous System (AS)

„ อาจจะเป็นหนึ่งองค์กร หรือ หนึ่ง ISP

„ องค์กรหนึ่งอาจจะแบ่งกลุ่มของ Router เป็น

หลาย AS ก็ได ้

„ Router ภายใน AS จะมีการแลกเปลี่ยน Routing

Information กัน

Chapter 27: 27.7 Two Type of

Internet Routing Protocol

„ 27.7.1 Interior Gateway

Protocols(IGP)

„ Router ภายใน AS จะใช ้ Interior Gateway

Protocol (IGP) ในการแลกเปลี่ยน Routing

Information

„ แต่ละ AS มีสิทธิ์ที่จะเลือก IGP อันใดก็ได ้

„ RIP

„ OSPF

„ IGRP (Cisco)

„ EIGRP (Cisco)

Chapter 27: 27.7 Two Type of

Internet Routing Protocol

„ 27.7.2 Exterior Gateway

Protocols(EGP)

„ Router ในแต่ละ AS จะใช ้ EGP ในการ

แลกเปลี่ยน Routing Information กับ Router

ในอีก AS หนึ่ง

„ EGP ปกติจะซับซ ้อนกว่า IGP แต่ว่าการใช ้งาน

จะยืดหยุ่นกว่า และมี Overhead ตํ่ากว่า

„ EGP จะสรุป Routing Information ในแต่ละ AS

ก่อนที่จะส่งไปให ้อีก AS หนึ่ง

„ การส่ง Routing Information ออกนอก AS สามารถ

กําหนดว่าข ้อมูลใดให ้ส่ง หรือไม่ให ้ส่งได ้

Chapter 27: 27.7 Two Type of

Internet Routing Protocol

„ 27.7.3 ต ัวอย่างการใช้งาน IGP และ EGP

„ Router R1 จะ Run ทั้ง IGP1 และ EGP

„ Router R4 จะ Run ทั้ง IGP2 และ EGP

Chapter 27: 27.7 Two Type of

Internet Routing Protocol

„ 27.7.4 Optimum Routes, Routing

Metrics and IGP

„ ปกติเส ้นทางส่งข ้อมูลใน Internet จะมีหลายเส ้นทาง

„ Router จะเลือกเส ้นทางที่ดีที่สุด (Optimal Routes)

„ Remote Application อาจจะเป็นเส ้นทางที่ Delay ตํ่าสุด

„ Web Application อาจเป็นเส ้นทางที่ Throughput สูงสุด

„ Webcast หรือ Real-Time อาจเป็นเส ้นทางที่ Jitter ตํ่าสุด

„ เราใช ้คําว่า Routing Metric เป็นตัววัดราคาของการส่ง

ในแต่ละเส ้นทาง

„ อาจจะวัดจาก Delay, Throughput หรือ Jitter หรือผสมกัน

„ แต่ปกติใน Internet จะใช ้ Metric สองตัวร่วมกัน

„ Hop Count (จํานวน Network หรือ Router ที่ผ่าน)

„ Administrative Cost (กําหนดเองจาก Administrator) เพื่อ

ควบคุมให ้เส ้นทางส่งข ้อมูลเป็นไปตามต ้องการ

„ เช่นกําหนดเส ้นทาง 4 Hop ให ้มี Administrative Cost ตํ่ากว่า

เส ้นทางสอง Hop เพื่อบังคับให ้ข ้อมูลส่งไปทางนี้

Chapter 27: 27.7 Two Type of

Internet Routing Protocol

„

27.7.4 Optimum Routes, Routing Metrics and

IGP

„

การหาเส ้นทางของ IGP จะใช ้ Routing Metric

„

EGP จะไม่ใช ้

„

เนื่องจากแต่ละ AS ใช ้ IGP ต่างกัน และใช ้ Metric ต่างกัน ไม่สามารถ

เปรียบเทียบได ้

„

ดังนั้น EGP จะไม่พยายามหา Optimal Path มันเพียงหาเส ้นทางส่ง

ข ้อมูลเท่านั้น

Throughput = 15 Mbps

AS 15

AS 1

AS 100

AS 70

Hop = 10

Chapter 27: 27.8 Routes and

Data Traffic

„ Data Traffic จะมีท ิศทางการใหลสวน

ทางก ับ Routing Traffic

Least Cost Path Algorithms

„

ดูรายละเอียดบทที่ 18 18.12-18.13

„

ดูจาก Course Notes วิชา CPE 326

„

ดูจาก Course Notes วิชา CPE 231

„

เรื่อง Graph

„

มีสอง Algorithm ที่ให้คําตอบเหมือนก ัน แต่ใช้วิธี

คํานวณต่างก ัน

„

ดังนั้นจะใช ้ข ้อมูลจาก Routing Information ต่างกัน

„

กําเนิดเป็นวิธีการ Routing สองแบบ

„

Distance Vector Routing จะใช ้ Bellman-Ford Algorithm

„

ในการนี้ Router จะแลกเปลี่ยนตาราง Routing Table เฉพาะกับเพื่อนบ ้าน

เท่านั้น ข ้อมูลจะ Propagate ทีละ Router เมื่อถึงเวลาแลกตาราง เช่น

RIP(Routing Information Protocol)

„

Link-State Routing จะใช ้ Dijkstra Algorithm

„

ในการนี้ Router จะส่ง Link State ของตนเอง (เฉพาะ Direct Connect) ไปให ้กับทุกๆ Router แต่ละ Router จะรวบรวม Link State Database และสร ้าง Topology ของทั้ง Network จากนั้นมันจะสร ้าง Shortest Path First Tree โดยตัวมันเป็น Root ไปยัง Router ทุกๆตัว

Least Cost Path Algorithms

NW3

NW2

R3

R2

NW4

R4

R5

NW7

R1

R6

NW1

R7

R9

R8

NW5

NW6

1. การส่งข้อมูลจาก Host หนึ่ง ไปย ังอีก Host หนึ่ง กระทําผ่าน Router ถ้าอยู่คนละ Network การหาเส้นทางคือหาเส้นทางจาก Router หนึ่งไปย ัง

อีก Router หนึ่ง ที่ Network น ั้นเชื่อมต่ออยู่

Least Cost Path Algorithms

R3

R2

R4

R5

R1

R6

R7

R9

R8

2. Cost ที่ส่งระหว่าง Router ไปและกล ับไม่จําเป็นต้องเท่าก ัน เพราะขึ้นอยู่

ก ับ Queue ที่ Interface ของ Router ต้นทาง ไม่ใช่ปลายทาง เราแสดง

ค่า Cost ระหว่าง Router ที่มีเส้นเชื่อมต่อ โดยใช้ Cost Matrix

Least Cost Path Algorithms

R3

5

1

R2

R4

4

2

2

1

R5

5

2

2

3

4

3

4

4

1

3 3 3

R1

R6

6

2

R7

4

5

5

1

R9

2 1

3

R8

5

2

3

2. Cost ที่ส่งระหว่าง Router ไปและกล ับไม่จําเป็นต้องเท่าก ัน เพราะขึ้นอยู่

ก ับ Queue ที่ Interface ของ Router ต้นทาง ไม่ใช่ปลายทาง เราแสดง

ค่า Cost ระหว่าง Router ที่มีเส้นเชื่อมต่อ โดยใช้ Cost Matrix (W)

Least Cost Path Algorithms

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

8

5

1

-

2

9

3

3

3

-

2. Cost ที่ส่งระหว่าง Router ไปและกล ับไม่จําเป็นต้องเท่าก ัน เพราะขึ้นอยู่

ก ับ Queue ที่ Interface ของ Router ต้นทาง ไม่ใช่ปลายทาง เราแสดง

ค่า Cost ระหว่าง Router ที่มีเส้นเชื่อมต่อ โดยใช้ Cost Matrix (W)

Bellman-Ford Algorithm

Definitions

„

Find shortest paths from given node subject to constraint that paths contain at most one link

„

Find the shortest paths with a constraint of paths of at most two links

„

And so on

„

s = source node

„

w(i, j) = link cost from node i to node j

„ w(i, i) = 0

„ w(i, j) = ∞ if the two nodes are not directly connected

„ w(i, j) ≥ 0 if the two nodes are directly connected

„

h = maximum number of links in path at current stage of the algorithm

„

Lh(n) = cost of least-cost path from s to n under constraint of no more than h links

Bellman-Ford Algorithm

Method

„

Step 1 [Initialization]

„ L0(n) = ∞, for all n ≠ s

„ Lh(s) = 0, for all h

„

Step 2 [Update]

„

For each successive h 0

„ For each n ≠ s, compute

„ Lh+1(n)=minj[Lh(j)+w(j,n)]; ∀j

„

Connect n with predecessor node j that achieves minimum

„

Eliminate any connection of n with different

predecessor node formed during an earlier

iteration

„

Path from s to n terminates with link from j to n

Example: Bellman Ford จาก Node

1 (h=0: Initialization: s=1)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไปทุกๆ Node = Infinity

8

5

1

-

2

L0(n)=∞; n = 2,..,9: L0(1)=0

9

3

3

3

-

Example: Bellman Ford จาก Node

1 (h=1: Initialization: s=1)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไปทุกๆ Node = Infinity

8

5

1

-

2

L0(n)=∞; n = 2,..,9: L0(1)=0

9

3

3

3

-

คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]

L1(2)=minj[L0(j)+w(j,2)]; j = 1,..,9

=min[L0(1)+w(1,2),L0(2)+w(2,2),L0(3)+w(3,2),…,L0(9)+w(9,2)]

=min j = 1, path = 1-2, cost = 3

L1(3)=minj[L0(j)+w(j,3)]; j = 1,..,9

=min[L0(1)+w(1,3),L0(2)+w(2,3),L0(3)+w(3,3),…,L0(9)+w(9,3)]

=all infinity

Example: Bellman Ford จาก Node

1 (h=2: n=2,3)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไป Node 3,4,5,7,9= Infinity

8

5

1

-

2

L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0

9

3

3

3

-

คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]

L2(2)=minj[L1(j)+w(j,2)]; j = 1,..,9

=min[L1(1)+w(1,2),L1(2)+w(2,2),L1(3)+w(3,2),…,L1(9)+w(9,2)]

=min j = 1, path = 1-2, cost = 3

L2(3)=minj[L1(j)+w(j,3)]; j = 1,..,9

=min[L1(1)+w(1,3),L1(2)+w(2,3),L1(3)+w(3,3),…,L1(9)+w(9,3)]

=min j=2, path = 1-2 plus 2-3 = 1-2-3, cost = 3+5=8

Example: Bellman Ford จาก Node

1 (h=2: n=5,7)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไป Node 3,4,5,7,9= Infinity

8

5

1

-

2

L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0

9

3

3

3

-

คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]

L2(5)=minj[L1(j)+w(j,5)]; j = 1,..,9

=min[L1(1)+w(1,5),L1(2)+w(2,5),L1(3)+w(3,5),…,L1(6)+w(6,5),..,L1(9)+w(9,5)]

=min(3+1,6+3)=4 (j=2, path = 1-2-5, cost = 4)

L2(7)=minj[L1(j)+w(j,7)]; j = 1,..,9

=min[L1(1)+w(1,7),L1(2)+w(2,7),…,L1(6)+w(6,7),…,L1(9)+w(9,7)]

=min j=6, path = 1-6 plus 6-7 = 1-6-7, cost = 6+2=8

Example: Bellman Ford จาก Node

1 (h=2: n=6)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไปทุกๆ Node = Infinity

8

5

1

-

2

L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0

9

3

3

3

-

คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]

L2(6)=minj[L1(j)+w(j,6)]; j = 1,..,9

=min[L1(1)+w(1,6),…, L1(8)+w(8,6),..,L1(9)+w(9,6)]

= j=8; Path 1-8+8-6 ถูกกว่า Path 1-6

Example: Bellman Ford จาก Node

1 (h=2: n=8)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไปทุกๆ Node = Infinity

8

5

1

-

2

L1(2)=3; L1(6)=6; L1(8)=2; : L1(1)=0

9

3

3

3

-

คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]

L2(8)=minj[L1(j)+w(j,8)]; j = 1,..,9

=min[L1(1)+w(1,8),…, L1(6)+w(6,8),..,L1(9)+w(9,8)]

=Path ไม่เปลี่ยน

กรณี n=9 พบว่า Path 1-8-9 มีอันเดียวที่มี 2 Hop

Example: Bellman Ford จาก Node

1 (h=3)

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

Cost R1 ไป Node 4 = Infinity

8

5

1

-

2

L2(2)=3; L2(3)=7; L2(5)=4; L2(6)=6

9

3

3

3

-

L2(7)=8; L2(8)=2; L2(9)=4: L2(1)=0

คํานวณ Lh+1(n)=minj[Lh(j)+w(j,n)]

L3(5)=minj[L2(j)+w(j,5)]; j = 1,..,9

=min[L2(1)+w(1,5),L2(2)+w(2,5),L2(3)+w(3,5),..,L1(9)+w(9,5)]

=Path ไม่เปลี่ยน

Path ไป R7 ไม่เปลี่ยน แม ้ว่า Path 1-2-5-7 จะเท่ากัน

Path ไป R3 เปลี่ยน จาก 1-2-3 เป็น 1-2-5-3, Path R4 = min(1-2-3-4,1-8-9-4)

Example: Bellman Ford จาก Node

1 (h=4)

R3

1

2

3

4

5

6

7

8

9

R2

R4

2

1

-

3

6

2

1

R5

2

2

-

5

1

3

3

4

-

1

5

3

R1

R6

2

4

2

-

3

3

R7

R9 5

2

2

-

4

1

2 1

R8

2

6

4

3

-

2

1

7

4

4

5

-

5

8

5

1

-

2

9

3

3

3

-

Algorithm จะหยุดเมื่อถึงจํานวน Hop สูงสุดของ NW

Algorithm สามารถคํานวณได้แม้ว่าจะไม่รู้ Topology โดยการร ับข้อมูลจาก Node ข้างเคียง แล้วมา Update ตารางของต ัวเอง โดยใช้ค่า Cost ที่ตํ่ากว่า

Dijkstra’s Algorithm

Definitions

„

Find shortest paths from given source node to all other nodes, by developing paths in order of increasing path length

„

N = set of nodes in the network

„

s = source node

„

T = set of nodes so far incorporated by the algorithm

„

w(i, j) =

link cost from node i to node j

„

w(i, i) = 0

„

w(i, j) = ∞ if the two nodes are not directly connected

„

w(i, j) ≥ 0 if the two nodes are directly connected

„

L(n) = cost of least-cost path from node s to node n currently known

„

At termination, L(n) is cost of least-cost path from s to n

Dijkstra’s Algorithm Method

„

Step 1 [Initialization]

„

T = {s} Set of nodes so far incorporated consists of only source node

„

L(n) = w(s, n) for n ≠ s

„

Initial path costs to neighboring nodes are simply link costs

„

Step 2 [Get Next Node]

„

Find neighboring node not in T with least-cost path from s

„

Incorporate node into T

„

Also incorporate the edge that is incident on that node and a node in T that contributes to the path

„

Step 3 [Update Least-Cost Paths]

„

L(n) = min[L(n), L(x) + w(x, n)] for all n ∉ T

„

If latter term is minimum, path from s to n is path from s to x concatenated with edge from x to n

„

Algorithm terminates when all nodes have been added to T

Example: Dijkstra จาก Node 1

(T={1})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1}, L(2)=3,L(3)=inf,L(4)=inf,

8

5

1

-

2

L(5)=inf,L(6)=6,L(7)=inf,L(8)=2,

9

3

3

3

-

L(9)=inf

Example: Dijkstra จาก Node 1

(T={1})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1}, L(2)=3,L(3)=inf,L(4)=inf,

8

5

1

-

2

L(5)=inf,L(6)=6,L(7)=inf, L(8)=2,

9

3

3

3

-

L(9)=inf

Min = L(8) ด ังน ั้นนํา Node 8 ใส่ใน T; T={1,8}

L(n) = min[L(n), L(8) + w(8, n)] for all n not in T

T={1,8}, L(2)=3,L(3)=inf,L(4)=inf,

L(5)=inf, L(6)=3, L(7)=inf,L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,8})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,8}, L(2)=3, L(3)=inf,L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2

L(5)=inf,L(6)=3,L(7)=inf, L(8)=2,

9

3

3

3

-

L(9)=4

Min = L(2) ด ังน ั้นนํา Node 2 ใส่ใน T; T={1,2,8}

L(n) = min[L(n), L(2) + w(2, n)] for all n not in T

T={1,2,8}, L(2)=3, L(3)=8, L(4)=inf,

L(5)=4, L(6)=3, L(7)=inf, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,8})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,2,8}, L(2)=3, L(3)=8,L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2

L(5)=4, L(6)=3, L(7)=inf, L(8)=2,

9

3

3

3

-

L(9)=4

Min = L(6) ด ังน ั้นนํา Node 6 ใส่ใน T; T={1,2,6,8}

L(n) = min[L(n), L(6) + w(6, n)] for all n not in T

T={1,2,6,8}, L(2)=3, L(3)=8, L(4)=inf,

L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,6,8})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,2,6,8}, L(2)=3, L(3)=8,L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2

L(5)=4, L(6)=3, L(7)=5, L(8)=2,

9

3

3

3

-

L(9)=4

Min = L(5) หรือ L(9) ก็ได้ ด ังน ั้นนํา Node 5 ใส่ใน T; T={1,2,5,6,8}

L(n) = min[L(n), L(5) + w(5, n)] for all n not in T

T={1,2,5,6,8}, L(2)=3, L(3)=6, L(4)=inf,

L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,5,6,8})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,2,5,6,8}, L(2)=3, L(3)=6, L(4)=inf, 8 5 ∞ ∞ ∞ ∞ 1 ∞ - 2

L(5)=4, L(6)=3, L(7)=5, L(8)=2,

9

3

3

3

-

L(9)=4

Min = L(9) ด ังน ั้นนํา Node 9 ใส่ใน T; T={1,2,5,6,8,9}

L(n) = min[L(n), L(9) + w(9, n)] for all n not in T

T={1,2,5,6,8,9}, L(2)=3, L(3)=6, L(4)=7,

L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,5,6,8,9})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,2,5,6,8,9}, L(2)=3, L(3)=6,

8

5

1

-

2

L(4)=7, L(5)=4, L(6)=3, L(7)=5,

9

3

3

3

-

L(8)=2, L(9)=4

Min = L(7) ด ังน ั้นนํา Node 7 ใส่ใน T; T={1,2,5,6,7,8,9}

L(n) = min[L(n), L(7) + w(7, n)] for all n not in T

T={1,2,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7,

L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,5,6,7,8,9})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,2,5,6,7,8,9}, L(2)=3, L(3)=6,

8

5

1

-

2

L(4)=7, L(5)=4, L(6)=3, L(7)=5,

9

3

3

3

-

L(8)=2, L(9)=4

Min = L(3) ด ังน ั้นนํา Node 3 ใส่ใน T; T={1,2,3,5,6,7,8,9}

L(n) = min[L(n), L(3) + w(3, n)] for all n not in T

T={1,2,3,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7, L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,3,5,6,7,8,9})

R3

5

1

1

2

3

4

5

6

7

8

9

R2

R4

4

2

2

1

-

3

6

2

1

R5

5

2

2

-

5

1

2

2

3

4

3

4

3

4

-

1

5

4

1

3 3 3

R1

R6

6

2

4

2

-

3

3

R7

4

5

5

1

R9 5

2

2

-

4

1

2 1

3

R8

5

2

6

4

3

-

2

1

3

7

4

4

5

-

5

T={1,2,3,5,6,7,8,9}, L(2)=3, L(3)=6,

8

5

1

-

2

L(4)=7, L(5)=4, L(6)=3, L(7)=5,

9

3

3

3

-

L(8)=2, L(9)=4

Min = L(4) ด ังน ั้นนํา Node 4 ใส่ใน T; T={1,2,3,4,5,6,7,8,9}

L(n) = min[L(n), L(4) + w(4, n)] for all n not in T

T={1,2,3,4,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7, L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4

Example: Dijkstra จาก Node 1

(T={1,2,3,4,5,6,7,8,9})

R3

1

2

3

4

5

6

7

8

9

R2

R4

2

1

-

3

6

2

1

R5

2

2

-

5

1

3

3

4

-

1

5

3

R1

R6

2

4

2

-

3

3

R7

R9 5

2

2

-

4

1

2 1

R8

2

6

4

3

-

2

1

7

4

4

5

-

5

8

5

1

-

2

9

3

3

3

-

T={1,2,3,4,5,6,7,8,9}, L(2)=3, L(3)=6, L(4)=7, L(5)=4, L(6)=3, L(7)=5, L(8)=2,

L(9)=4 Algorithm Terminates

Dijkstra จะคํานวณได้ต่อเมื่อรู้ Topology ของ Network

HW # 7

„ Download และส่งส ัปดาห ์หน้า

End of Week 12

„ Week 13 IP Routing II:

BGP/RIP/OSPF and Multicast

Protocols

„ Chapter 27:27.9-27.16 + Extra Notes

„ BGP

„ RIP

„ OSPF

„ Subnet and VLAN

„ Switch Layer 3

previous page start